Lãnh đạo NKVD trước đây Genrikh Yagoda, Vyacheslav Menzhinsky và Felix Dzerzhinsky, 1924

Sau Cách mạng Tháng Hai Nga năm 1917, Chính phủ lâm thời đã giải tán Binh đoàn Hiến binh đặc biệt (tiếng Nga: Отдельный корпус жандармов), Nha Cảnh vệ (tiếng Nga: Департамент Полиции) của Sa hoàng và thiết lập Narodnyj Militsiya (Cảnh sát Nhân dân). Sau đó diễn ra Cách mạng Tháng Mười năm 1917 với sự lãnh đạo bởi Lenin và Bolshevik đã giành chính quyền và thiết lập chính quyền Bolshevik mới, Cộng hòa Xã hội chủ nghĩa Xô viết Liên bang Nga hay còn gọi Nga Xô (RSFSR). Bộ Nội vụ (MVD) Chính phủ lâm thời trước đây dưới quyền Georgy Lvov (từ tháng 3 năm 1917), Nikolai Avksentiev (từ 6 tháng 8 [lịch cũ 24 tháng 7] năm 1917), Alexei Nikitin (từ 8 tháng 10 [lịch cũ 25 tháng 9] năm 1917), được chuyển thành Bộ Dân ủy Nội vụ (NKVD) dưới quyền Ủy viên Nhân dân. Tuy nhiên, NKVD bị quá tải bởi kế thừa các nhiệm vụ từ MVD, chẳng hạn như giám sát chính quyền địa phương và cứu hỏa, và Cảnh sát Công nhân và Nông dân (рабоче-крестьянской милиции) chịu trách nhiệm bởi những người vô sản hầu hết đều thiếu kinh nghiệm và không đủ chuyên môn. Nhận thấy rằng không có lực lượng an ninh đủ năng lực, Hội đồng Dân ủy Nga Xô thành lập ngày (20 tháng 12 [lịch cũ 7 tháng 12] năm 1917) lực lượng cảnh sát chính trị mật, Ủy ban Đặc biệt toàn Nga (Всеросси́йская чрезвыча́йная коми́ссия, Cheka), lãnh đạo bởi Felix Dzerzhinsky. Ủy ban đã giành được quyền tiến hành xét xử và hành quyết phi tư pháp nhanh chóng, nếu điều đó được coi là cần thiết để "bảo vệ cuộc cách mạng Cộng sản - xã hội chủ nghĩa Nga".

Cheka được tổ chức lại vào năm 1922 thành Cục Chính trị Quốc gia, hoặc GPU (Государственное политическое управление, Gosudarstvennoe politicheskoe upravlenie), thuộc NKVD Nga Xô.[2] Năm 1922 Liên Xô thành lập, với Nga Xô là nước Cộng hòa Liên bang lớn nhất. GPU đã trở thành Cục Chính trị Quốc gia toàn liên bang (Объединённое государственное политическое управление, Obyedinyonnoye gosudarstvennoye politicheskoye upravleniye, OGPU), thuộc Hội đồng Dân ủy Liên Xô, trở thành cơ quan ngang Bộ. NKVD Nga Xô duy trì quyền kiểm soát militsiya và nhiều trách nhiệm khác.

Năm 1934 NKVD Nga Xô được chuyển đổi thành một lực lượng an ninh toàn liên bang, NKVD Liên Xô (mà các nhà lãnh đạo Đảng Cộng sản Liên Xô gọi là "đội ngũ quan trọng của đảng chúng ta"), và OGPU được hợp nhất vào NKVD với tên gọi là Tổng cục An ninh Quốc gia (GUGB); NKVD riêng biệt của Nga Xô không được phục hồi cho đến năm 1946 (là Bộ Nội vụ Nga Xô). Do đó, NKVD cũng nắm quyền kiểm soát tất cả các cơ sở giam giữ (bao gồm các trại lao động, được biết tới là GULag) cũng như cảnh sát chính quy. Vào những thời điểm khác nhau, NKVD có các Tổng cục sau, viết tắt "ГУ"– Главное управление, Glavnoye upravleniye.

ГУГБ – государственной безопасности, Tổng cục An ninh Quốc gia (GUGB, Glavnoye upravleniye gosudarstvennoi bezopasnosti)ГУРКМ– рабоче-крестьянской милиции, Tổng cục Cảnh sát Công nhân và Nông dân (GURKM, Glavnoye upravleniye raboče-krest'yanskoi militsyi)ГУПВО– пограничной и внутренней охраны, Tổng cục An ninh Biên giới và Nội vụ (GUPVO, GU pograničnoi i vnytrennei okhrany)ГУПО– пожарной охраны, Tổng cục Phòng cháy chữa cháy (GUPO, GU požarnoi okhrany)ГУШосДор– шоссейных дорог, Tổng cục Cao tốc (GUŠD, GU šosseynykh dorog)ГУЖД– железных дорог, Tổng cục Đường sắt (GUŽD, GU železnykh dorog)ГУЛаг– Главное управление исправительно-трудовых лагерей и колоний, Tổng cục Trại giam (GULag, Glavnoye upravleniye ispravitelno-trudovykh lagerey i kolonii)ГЭУ – экономическое, Tổng cục Kinh tế (GEU, Glavnoye ekonomičeskoie upravleniye)ГТУ – транспортное, Tổng cục Giao thông (GTU, Glavnoye transportnoie upravleniye)ГУВПИ – военнопленных и интернированных, Tổng cục Tù binh và giam giữ cá nhân (GUVPI, Glavnoye upravleniye voyennoplennikh i internirovannikh)

Thời kỳ Yezhov

Cho đến khi Nikolai Yezhov bắt đầu tái tổ chức với cuộc thanh trừng cảnh sát mật địa phương vào mùa thu năm 1936 và chính thức hóa vào tháng 5 năm 1939 theo đó tất cả các cuộc bổ nhiệm cho cảnh sát mật địa phương đều được kiểm soát từ trung ương trực tiếp là NKVD Liên Xô chỉ đạo, trước đây đã thường xuyên xảy ra căng thẳng giữa trung ương kiểm soát tập trung các đơn vị địa phương, và sự cấu kết của các đơn vị này với các đảng phái địa phương và khu vực, dẫn đến việc phá hỏng các kế hoạch từ Moskva.[3]

Sau khi thành lập vào năm 1934, NKVD đã trải qua nhiều thay đổi về tổ chức; riêng từ năm 1938 đến năm 1939, cơ cấu và ban lãnh đạo của NKVD đã thay đổi ba lần.

Trong thời gian Yezhov nắm quyền, cuộc Đại thanh trừng lên đến đỉnh điểm chỉ tính riêng từ những năm 1937 và 1938, ít nhất 1.3 triệu người bị bắt và 681,692 người bị hành quyết vì 'tội danh chống lại nhà nước'. Gulag tăng 685,201 người dưới thời Yezhov, gần gấp ba quy mô chỉ trong hai năm, với ít nhất 140,000 tù nhân (có thể nhiều hơn) chết vì suy dinh dưỡng, kiệt sức và các yếu tố trong trại giam (hoặc trong quá trình vận chuyển).[4]

Vào ngày 3 tháng 2 năm 1941, vụ 4 (Bộ phận Đặc biệt, OO) thuộc GUGB NKVD cơ quan an ninh chịu trách nhiệm về hoạt động chống phản gián trong Lực lượng vũ trang Liên Xô,[5] bao gồm 12 Bộ phận và một Đơn vị Điều tra, được tách ra khỏi GUGB NKVD Liên Xô.

Việc giải thể OO GUGB trong NKVD được công bố vào ngày 12 tháng 2 theo nghị định liên tịch số 00151/003 của NKVD và Bộ Dân ủy An ninh Quốc gia (NKGB) Liên Xô. Các cơ quan còn lại của GUGB đã bị bãi bỏ và nhân viên được chuyển đến NKGB mới được thành lập. Các vụ của GUGB trước đây được đổi tên thành Cục. Ví dụ, đơn vị tình báo nước ngoài được gọi là Vụ Ngoại giao (INO) trở thành Cục Đối ngoại (INU); Đơn vị cảnh sát mật GUGB do Vụ Chính trị Bí mật (SPO) trở thành Cục Chính trị Bí mật (SPU),... và tương tự. Vụ 4 GUGB (OO) trước đây được chia thành ba bộ phận. Một bộ phận xử lý phản gián quân sự trong lực lượng NKVD (trước đây Bộ phận 11 của vụ 4 GUGB) trở thành vụ 3 NKVD hoặc OKR (Otdel KontrRazvedki), lãnh đạo OKR NKVD là Aleksander Belyanov.

Sau khi Đức tấn công Liên Xô (tháng 6/1941), NKGB Liên Xô bị giải thể và ngày 20 tháng 7 năm 1941 các đơn vị của NKGB trở thành một phần của NKVD Liên Xô. Lực lượng CI cũng được nâng cấp từ vụ thành cục và trực thuộc tổ chức NKVD (Tổng cục Đặc biệt hoặc UOO NKVD Liên Xô). Bộ phận duy nhất không quay trở lại UOO NKVD cho đến ngày 11 tháng 1 năm 1942 là bộ phận chịu trách nhiệm về phản gián trong NKVMF (Hải quân). Bộ phận quay trở lại quyền kiểm soát của NKVD vào ngày 11 tháng 1 năm 1942 với tư cách là Vụ 9 UOO do P. Gladkov lãnh đạo. Vào tháng 4 năm 1943, Tổng cục Đặc biệt được chuyển thành Cục Diệt gián điệp (SMERSH) và chuyển sang Bộ Dân ủy Quốc phòng và các Bộ Dân ủy quản lý. Đồng thời, NKVD giảm quy mô và nhiệm vụ bằng cách thành lập lại NKGB.

Năm 1946, tất cả Bộ Dân ủy được gọi là "Bộ". Theo đó, Bộ Dân ủy Nội vụ (NKVD) Liên Xô trở thành Bộ Nội vụ (MVD), trong khi NKGB được đổi tên thành Bộ An ninh Quốc gia (MGB).

Năm 1953, sau khi Lavrenty Beria bị bắt, MGB sát nhập lại với MVD. Các ngành cảnh sát và an ninh cuối cùng đã tách ra vào năm 1954 để trở thành:

• Bộ Nội vụ Liên Xô (MVD), chịu trách nhiệm về lực lượng dân quân chống tội phạm và các cơ sở cải huấn.
• Ủy ban An ninh Quốc gia Liên Xô (KGB), chịu trách nhiệm về cảnh sát mật, tình báo, phản gián, bảo vệ cá nhân (của giới lãnh đạo) và thông tin liên lạc bí mật.